Given a graph G=(V,E), a set of vertices S ⊆ V covers v ∈ V if the edge connectivity between S and v is at least a given number k. Vertices in S are called sources. The source location problem is a problem of finding a minimum-size source set covering all vertices of a given graph. This paper presents a new variation of the problem, called maximum-cover source-location problem, which finds a source set S with a given size p, maximizing the sum of the weight of vertices covered by S. It presents an O(np + m + nlog n)-time algorithm for k=2, where n=|V| and m=|E|. Especially it runs linear time if G is connected. This algorithm uses a subroutine for finding a subtree with the maximum weight among p-leaf trees of a given vertex-weighted tree. For the problem we give a greedy-based linear-time algorithm, which is an extension of the linear-time algorithm for finding a longest path of a given tree presented by E. W. Dijkstra around 1960. Moreover, we show some polynomial solvable cases, e.g., a given graph is a tree or (k-1)-edge-connected, and NP-hard cases, e.g., a vertex-cost function is given or G is a digraph.

H-coloring problem is a coloring problem with restrictions such that some pairs of colors cannot be used for adjacent vertices, where H is a graph representing the restrictions of colors. We deal with the case that H is the complement graph of a cycle of odd order 2p + 1. This paper presents the following results: (1) chordal graphs and internally maximal planar graphs are -colorable if and only if they are p-colorable (p 2), (2) -coloring problem on planar graphs is NP-complete, and (3) there exists a class that includes infinitely many -colorable but non-3-colorable planar graphs.

The statistical behavior of the amplitude probability distribution of intermodulation distortion interference in multichannel optical-cable TV systems was experimentally investigated. In multichannel transmission, the non-linearity of a laser diode (LD) or an electrical amplifier can cause intermodulation distortion (composite-second-order beat; CSO, composite-triple-beat; CTB, etc. ). Even though it has been discussed as laser-clipping distortion, intermodulation distortion is usually distortion from AM-VSB carriers. The statistical analysis and evaluation of the distortion in transmitted channel is in controversial. We evaluated the distortion in 20 frequency-division-multiplexed 16-QAM channels, with each carrier carrying 80 Mbps for an optical cable TV system. We first enumerated the distortion components causing interference in each transmission channel so as to identify the intermodulation products. Then, in selected channels, we precisely measured the power of each kind of distortion and the amplitude distributions of the intermodulation distortion from sinusoidal and digital-modulated carriers on cable TV as a function of optical modulation depth (OMD) of LD. And we clarified how the probability distribution function (PDF) changed as the OMD increased. Also, the BER performance of a 16-QAM signal was measured and compare to the intermodulation behavior of the different distortion sources. We found evidence that the amplitude distribution of intermodulation distortion from digital carriers differs from that of thermal noise. Experimental results showed that the PDF of the intermodulation distortion changed when the ratio of intermodulation distortion among all undesired signals varied with the OMD. The BER performance varied with intermodulation of both analogue and digital carriers even when the carrier to interference noise power ratio (CIR) is the same.

To realize a highly efficient small antenna, high-Tc superconductors are adopted to fabricate both a self-resonating helical radiator and a quarter-wave matching circuit. The actual gain and bandwidth measured at 478 MHz using a 1/45-wavelength radiator were respectively 1.5 dBi and 0.35%, indicating that this type of antenna has a high radiation efficiency and a fairly wide bandwidth. It is also confirmed through experiments and theoretical simulations that a decrease in the surface resistance of the radiator more effectively improves the radiation efficiency than a decrease in the surface resistance of the matching circuit.

This paper proposed the method as an estimation on the size of discharge spots through observation on traces after the discharge arose in circumstances gases mixed hydrocarbon gas. Namely, the circular carbonaceous deposit and the carbonaceous heap are observed on cathode and anode surface, respectively, after the short gap discharge arises in N2+NO+CH4 gases. The current density, which is the normal conversion current density, is calculated from the size of the trace of discharge and its value is about 1.010-9 A/(cm2 Pa2) in case that the concentration of CH4 is 0.6%. The value is about 1/5 of values that are reported in the former articles and is reasonable one.

The statistical behavior of the amplitude probability distribution of intermodulation distortion interference in multichannel optical-cable TV systems was experimentally investigated. In multichannel transmission, the non-linearity of a laser diode (LD) or an electrical amplifier can cause intermodulation distortion (composite-second-order beat; CSO, composite-triple-beat; CTB, etc. ). Even though it has been discussed as laser-clipping distortion, intermodulation distortion is usually distortion from AM-VSB carriers. The statistical analysis and evaluation of the distortion in transmitted channel is in controversial. We evaluated the distortion in 20 frequency-division-multiplexed 16-QAM channels, with each carrier carrying 80 Mbps for an optical cable TV system. We first enumerated the distortion components causing interference in each transmission channel so as to identify the intermodulation products. Then, in selected channels, we precisely measured the power of each kind of distortion and the amplitude distributions of the intermodulation distortion from sinusoidal and digital-modulated carriers on cable TV as a function of optical modulation depth (OMD) of LD. And we clarified how the probability distribution function (PDF) changed as the OMD increased. Also, the BER performance of a 16-QAM signal was measured and compare to the intermodulation behavior of the different distortion sources. We found evidence that the amplitude distribution of intermodulation distortion from digital carriers differs from that of thermal noise. Experimental results showed that the PDF of the intermodulation distortion changed when the ratio of intermodulation distortion among all undesired signals varied with the OMD. The BER performance varied with intermodulation of both analogue and digital carriers even when the carrier to interference noise power ratio (CIR) is the same.

We present constant-time testing algorithms for generalized shogi (Japanese chess), chess, and xiangqi (Chinese chess). These problems are known or believed to be EXPTIME-complete. A testing algorithm (or a tester) for a property accepts an input if it has the property, and rejects it with high probability if it is far from having the property (e.g., at least 2/3) by reading only a constant part of the input. A property is said to be testable if a tester exists. Given any position on a ⌊√n⌋×⌊√n⌋ board with O(n) pieces, the generalized shogi, chess, and xiangqi problem are problems determining the property that “the player who moves first has a winning strategy.” We propose that this property is testable for shogi, chess, and xiangqi. The shogi tester and xiangqi tester have a one-sided-error, but surprisingly, the chess tester has no-error. Over the last decade, many problems have been revealed to be testable, but most of such problems belong to NP. This is the first result on the constant-time testability of EXPTIME-complete problems.

Unlike the conventional plasma-TVs using the driving circuit with two polarities during the reset and address periods, the cost-effective driving circuit using only the positive voltage level during the reset and address periods is proposed and implemented in the 42-in. plasma-TV.

In this paper, we study lower bounds on the query complexity of testing algorithms for various problems. Given an oracle that returns information of an input object, a testing algorithm distinguishes the case that the object has a given property P from the case that it has a large distance to having P with probability at least . The query complexity of an algorithm is measured by the number of accesses to the oracle. We introduce two reductions that preserve the query complexity. One is derived from the gap-preserving local reduction and the other is from the L-reduction. By using the former reduction, we show linear lower bounds on the query complexity for testing basic NP-complete properties, i.e., 3-edge-colorability, directed Hamiltonian path/cycle, undirected Hamiltonian path/cycle, 3-dimensional matching and NP-complete generalized satisfiability problems. Also, using the second reduction, we show a linear lower bound on the query complexity of approximating the size of the maximum 3-dimensional matching.

Coloring problem is a well-known combinatorial optimization problem of graphs. This paper considers H-coloring problems, which are coloring problems with restrictions such that some pairs of colors can not be used for adjacent vertices. The restriction of adjacent colors can be represented by a graph H, i.e., each vertex represents a color and each edge means that the two colors corresponding to the two end-vertices can be used for adjacent vertices. Especially, H-coloring problem with a complete graph H of order k is equivalent to the traditional k-coloring problem. This paper presents sufficient conditions such that H-coloring problem can be reduced to an H-coloring problem, where H is a subgraph of H. And it shows a hierarchy about classes of H-colorable graphs for any complement graph H of a cycle of order odd n 5.

In this paper, we propose a channel assignment scheme for integrated voice and data traffic in reservation multiple access protocol. In the proposed scheme, a voice packet never contends with a data packet and takes over the slot which is previously assigned to a data packet. Thus, a larger number of voice terminals can be accommodated without degradation of quality and throughput even in the situation that data were integrated. We evaluate the voice packet dropping probability, throughput and packet delay through computer simulation. The results show that the proposed scheme has better performance than the conventional PRMA and DQRUMA systems.

We experimentally studied the polarization mode dispersion (PMD) tolerance of an feed-forward equalizer (FFE) electronic dispersion compensation (EDC) IC in the absence of adaptive control, in 43-Gbit/s RZ-DQPSK transmission. Using a 3-tap FFE IC composed of InP HBTs, differential group delay (DGD) tolerance at a 2-dB Q penalty is shown to be extended from 25 ps to up to 29 ps. When a polarization scrambler is used, the tolerance is further extended to 31 ps. This value is close to the tolerance obtained with adaptive control, without a polarization scrambler.

For the expansion of using the integral equation methods on wave-field analysis, a new method called "Source and Radiation Field Solution" is suggested. This solution uses a couple of integral equations. One of them is the traditional integral expression giving the scattered field from the wave source, another is newly proposed one which expresses the wave source from both of the source and the scattered field, by using the conjugate Green function expression. Therefore this method can derive both of the source and the scattered field at the same time by coupled two equations. For showing the effect of this method, we analyze scattering problems for dielectrics in this paper.

In this paper, we study a problem of inferring blood relationships which satisfy a given matrix of genetic distances between all pairs of n nodes. Blood relationships are represented by our proposed graph class, which is called a pedigree graph. A pedigree graph is a directed acyclic graph in which the maximum indegree is at most two. We show that the number of pedigree graphs which satisfy the condition of given genetic distances may be exponential, but they can be represented by one directed acyclic graph with n nodes. Moreover, an O(n3) time algorithm which solves the problem is also given. Although phylogenetic trees and phylogenetic networks are similar data structures to pedigree graphs, it seems that inferring methods for phylogenetic trees and networks cannot be applied to infer pedigree graphs since nodes of phylogenetic trees and networks represent species whereas nodes of pedigree graphs represent individuals. We also show an O(n2) time algorithm which detects a contradiction between a given pedigree graph and distance matrix of genetic distances.

We study effects of preamplifier nonlinearity on polarization mode dispersion (PMD) equalization performance of feed-forward equalizer (FFE) electronic dispersion compensation (EDC) IC. We have shown that a nonlinear limiting amplifier can be used as a preamplifier for FFE EDC IC for a 6-dB dynamic range.

Connectivity (of node-to-node) is generally used to examine the robustness of graphs. When telecommunication network switches are integrated into logical switching areas, we should examine node-to-area connectivity rather than node-to-node connectivity. In a previous paper, we proposed node-to-area (NA) connectivity using area (subset of nodes) graph. In this paper, we consider a further constraint: "there is a path that does not include other nodes in the source node area." We call this property, directly NA-connected. Application of this constraint makes telecommunications networks robust against locally striking disasters. The problem of finding the maximum number of edge deletions that still preserves the direct NA-connection is shown to be NP-hard. It was shown in our previous paper that an NA-connected spanning tree is easily found; this paper shows that the problem of finding a directly NA-connected spanning tree is also NP-hard. We propose an O(|E||X|) approximation algorithm that finds a directly NA-connected spanning subgraph with an edge nummber not exceeding 2|V|3 for any NA-connected area graph that satisfies a described simple condition. (|V|,|E|,and |X| are the numbers of nodes, edges, and areas, respectively.)

We study a reconfiguration problem for Steiner trees in an unweighted graph, which determines whether there exists a sequence of Steiner trees that transforms a given Steiner tree into another one by exchanging a single edge at a time. In this paper, we show that the problem is PSPACE-complete even for split graphs, while solvable in linear time for interval graphs and for cographs.

Streak cameras are now widely used for measurements of ultra short phenomena, such as those in semi conductor luminescence and plasma gaseous discharge. To further improve the temporal resolution and carry out higher-dimensional measurements, it is necessary to understand the electron beam behavior in detail. Thus, numerical simulations play an important role in the analysis of the streak camera. The authors have been working on the development of a numerical simulation code that uses the finite difference method (FDM) for electric field analysis, the Runge-Kutta (R-K) method for charged particle motion determination, and the particle-in-cell (PIC) method for charge density calculation. However, the use of the PIC method leads to inaccuracy in the charge density calculation in cases of high-density electron beams. To improve the accuracy of the conventional analysis of the streak camera, we perform the boundary element (BE) analysis of the streak camera.

We introduce the notion of 'Composition', 'Union' and 'Division' of cellular automata on groups. A kind of notions of compositions was investigated by Sato [10] and Manzini [6] for linear cellular automata, we extend the notion to general cellular automata on groups and investigated their properties. We observe the all unions and compositions generated by one-dimensional 2-neighborhood cellular automata over Z2 including non-linear cellular automata. Next we prove that the composition is right-distributive over union, but is not left-distributive. Finally, we conclude by showing reformulation of our definition of cellular automata on group which admit more than three states. We also show our formulation contains the representation using formal power series for linear cellular automata in Manzini [6].

We study the problem of transforming one list (vertex) coloring of a graph into another list coloring by changing only one vertex color assignment at a time, while at all times maintaining a list coloring, given a list of allowed colors for each vertex. This problem is known to be PSPACE-complete for bipartite planar graphs. In this paper, we first show that the problem remains PSPACE-complete even for bipartite series-parallel graphs, which form a proper subclass of bipartite planar graphs. We note that our reduction indeed shows the PSPACE-completeness for graphs with pathwidth two, and it can be extended for threshold graphs. In contrast, we give a polynomial-time algorithm to solve the problem for graphs with pathwidth one. Thus, this paper gives sharp analyses of the problem with respect to pathwidth.